前面有講過樹的基本概念和結構,這邊會講二元樹的應用,樹狀演算法大都是用鏈結串列來處理,鏈結串列的指標用來處理樹相當方便,只需改變指標即可,也可用陣列的連續記憶體來表示二元樹,至於使用陣列或鏈結串列有好有壞。
🌳 完滿二元樹(Full Binary Tree)
當二元樹的高度為h,樹的節點為2^-1,h>=0,則稱為「完滿二元樹」。
🌳 完整二元樹(Complete Binary Tree)
當二元樹的深度為h,所含的節點數小於2^h-1,其節點的編號方式如同深度h的完滿二元樹一樣,從左到右,由上到下的順序一一對應。
🌳 歪斜樹(Skewed Binary Tree)
當一個二元樹完全沒有左節點或右節點時,則稱為左歪斜樹或右歪斜樹。
🌳 嚴格二元樹(Strictly Binary Tree)
指二元樹的每個非終端點均有非空的左右子樹。
使用循序的一維陣列表示二元樹,先將此二元樹想成一個完滿二元樹,且第n個階度具有2^n-1個節點,並依序存放在此一維陣列中。
先來看看使用一維陣列建立二元樹的表示方法及索引值的配置:
可以看到此一維陣列的索引值的關係
左子樹索引值是父節點索引值 * 2。
右子樹索引值是父節點索引值 * 2+1。
這邊來看如何以一維陣列建立二元樹,也就是建立一個二元搜尋樹,是很好的排序應用模式,因為在建立二元樹時,資料已經有初步的比較判斷,並依照二元樹的建立規則來存放資料。
二元搜尋樹特點:
🪴 可以是空集合,但若不是空集合則節點上一定要有一個鍵值。
🪴 每一個樹根的值需大於左子樹的值。
🪴 每一個樹根的值需小於右子樹的值。
🪴 左子樹也是二元搜尋樹。
🪴 樹的每個節點值都不相同。
將一組資料40,20,10,50,30,建立一顆二元搜尋樹
範例:
// 定義一個二元樹節點
struct TreeNode {
data: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
impl TreeNode {
fn new(data: i32) -> Self {
TreeNode {
data,
left: None,
right: None,
}
}
// 插入數據到二元搜尋樹
fn insert(&mut self, data: i32) {
if data < self.data {
if let Some(left) = &mut self.left {
left.insert(data);
} else {
self.left = Some(Box::new(TreeNode::new(data)));
}
} else {
if let Some(right) = &mut self.right {
right.insert(data);
} else {
self.right = Some(Box::new(TreeNode::new(data)));
}
}
}
fn to_array(&self, array: &mut Vec<i32>) {
if let Some(left) = &self.left {
left.to_array(array);
}
array.push(self.data);
if let Some(right) = &self.right {
right.to_array(array);
}
}
}
fn main() {
let data = vec![40,20,10,50,30];
// 創建一個空的二元搜尋樹
let mut root: Option<Box<TreeNode>> = None;
// 依次插入數據
for value in data.iter() {
if let Some(ref mut node) = root {
node.insert(*value);
} else {
root = Some(Box::new(TreeNode::new(*value)));
}
}
// 轉化二元搜尋樹為一維陣列
let mut result = Vec::new();
if let Some(ref node) = root {
node.to_array(&mut result);
}
println!("{:?}", result);
}
接下來會繼續來學習各種二元樹的實作,搭配圖文好了解多了。
目前應該不會太難吧🌻🌻!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。